package com.leetcode;

/**
 * 494. 目标和
 *
 * @author fy
 * @date 2022/3/29 22:21
 */
public class Solution494 {

    private int count = 0;

    public int findTargetSumWays(int[] nums, int target) {
        calcSum(nums, target, 0, 0);
        return count;
    }

    /**
     * 计算目标值为target的和sum
     *
     * @param nums   要计算的数组
     * @param target 计算目标值
     * @param index  当前计算的第几个元素
     * @param sum    当前计算和
     */
    private void calcSum(int[] nums, int target, int index, int sum) {
        if (index == nums.length) {
            if (target == sum) {
                count++;
            }
            return;
        }
        calcSum(nums, target, index + 1, sum + nums[index]);
        calcSum(nums, target, index + 1, sum - nums[index]);
    }

    public static void main(String[] args) {
        int[] nums = new int[]{1, 1, 1, 1, 1};
        int target = 3;

        int n = new Solution494().findTargetSumWays(nums, target);
        System.out.println(n);
    }

}
